package day34_778;


/**
 * @ClassName Solution
 * @Description 二分+DFS
 * @Author clockTown
 * @Date 2021/6/12 15:37
 * @Version 1.0
 */
public class Solution {

    private int n;
    private int[][] grid;
    private int[] dx = {-1, 1, 0, 0};
    private int[] dy = {0, 0, -1, 1};

    public int swimInWater(int[][] grid) {
        n = grid.length;
        this.grid = grid;
        int left = Math.max(grid[0][0], grid[n - 1][n - 1]);
        int right = n * n - 1;
        while (left <= right) {
            int mid = (right + left) / 2;
            if (dfs(mid, 0, 0, new boolean[n][n])) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private boolean dfs(int t, int x, int y, boolean[][] visited) {
        if (x == n - 1 && y == n - 1) {
            return true;
        }
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] <= t) {
                if (dfs(t, nx, ny, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
}
